package zero.slr;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import zero.entity.Production;

/**
 * 项目规范集族
 * 
 * @author Zero
 *
 */
public class ItemSetFamily {
    private List<ItemSet>    itemSets = new ArrayList<>();
    private List<Production> productions;

    public ItemSetFamily() {

    }

    public ItemSetFamily(List<Production> productions) {
        this.productions = productions;
    }

    public void init() {
        Item    item    = Item.fromProduction(productions.get(0));
        ItemSet itemSet = makeItemSet(item);
        addItemSet(itemSet);

        Queue<ItemSet> queue = new LinkedList<>();

        // 0号项目规范集入队
        queue.add(itemSet);

        // 广度有限搜索，求项目集族
        while (!queue.isEmpty()) {
            itemSet = queue.remove();
            expand(itemSet, queue);
        }
    }

    // 扩张
    public void expand(ItemSet itemSet, Queue<ItemSet> queue) {
        List<Item> items     = itemSet.getItems();

        boolean[]  isVisited = new boolean[items.size()];
        for (int i = 0; i < items.size(); ++i) {
            isVisited[i] = false;
        }

        for (int i = 0; i < items.size(); ++i) {
            Item item = items.get(i);
            int  pos  = item.getPos();

            // 如果圆点到了最后一个，或者在超前试探的时候已经处理过了就不用扩展了
            if (pos == item.getRight().size() || isVisited[i]) {
                continue;
            }

            String trigger  = item.getRight().get(pos);
            Item   nextItem = (Item) item.clone();
            nextItem.step();

            ItemSet nextItemSet = makeItemSet(nextItem);

            for (int j = i + 1; j < items.size(); ++j) {
                Item item1 = items.get(j);

                if (item1.getPos() == item1.getRight().size() || isVisited[j]) {
                    continue;
                }

                if (item1.getRight().get(item1.getPos()).equals(trigger)) {
                    // 如果是同一个trigger，考虑状态合并

                    Item nextItem1 = (Item) item1.clone();
                    nextItem1.step();

                    ItemSet nextItemSet1 = makeItemSet(nextItem1);
                    nextItemSet.merge(nextItemSet1);

                    isVisited[j] = true;
                }
            }

            // 如果项目规范集中已经存在了，则直接加个箭头即可
            if (this.itemSets.contains(nextItemSet)) {
                itemSet.getGoMap().put(trigger, itemSets.get(itemSets.indexOf(nextItemSet)));
                continue;
            }

            // 加入到项目规范集族中
            addItemSet(nextItemSet);
            //System.out.println(nextItemSet.toString());
            // 添加跳转信息
            itemSet.getGoMap().put(trigger, nextItemSet);
            // 添加到队列中等到被扩展
            queue.add(nextItemSet);
        }
    }

    public ItemSet makeItemSet(Item item) {
        ItemSet itemSet = new ItemSet();

        itemSet.addAll(getClosure(item));

        return itemSet;
    }

    public List<Item> getClosure(Item item) {
        List<Item> closure   = new ArrayList<>();
        boolean    isChanged = false;
        int        number    = 0;

        item.setNumber(number++);
        closure.add(item);

        do {
            isChanged = false;

            for (int i = 0; i < closure.size(); ++i) {
                Item         it    = closure.get(i);
                List<String> right = it.getRight();

                if (it.getPos() == right.size()) {
                    // 忽略圆点在最后一个位置的项目
                    continue;
                }

                // 找it右部中小圆点后面的那个元素
                String b = right.get(it.getPos());

                if (Parser.getInstance().isTerminator(b)) {
                    continue;
                }

                for (Production p : productions) {
                    if (p.getLeft().equals(b)) {
                        Item x = Item.fromProduction(p);
                        if (!closure.contains(x)) {
                            x.setNumber(number++);
                            closure.add(x);
                            isChanged = true;
                        }
                    }
                }
            }
        } while (isChanged);

        return closure;
    }

    public void addItemSet(ItemSet itemSet) {
        itemSet.setNumber(itemSets.size());
        this.itemSets.add(itemSet);

    }

    @Override
    public String toString() {
        StringBuffer buf = new StringBuffer();

        for (ItemSet itemSet : itemSets) {
            buf.append(itemSet.toString());
        }

        return buf.toString();
    }

    public List<ItemSet> getItemSets() {
        return itemSets;
    }

    public void setItemSets(List<ItemSet> itemSets) {
        this.itemSets = itemSets;
    }

    public List<Production> getProductions() {
        return productions;
    }

    public void setProductions(List<Production> productions) {
        this.productions = productions;
    }
}
